深入理解Mysql索引底层数据结构与算法

索引（index）是帮助MySQL高效获取数据的一种有序数据结构。在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法，这种数据结构就是索引。

优势：

劣势：

数据结构学习网址

MSQL的索引是在存储引擎层实现的，不同的存储引擎有不同的结构，主要包含以下几种：

二叉树缺点：顺序插入时，会形成一个链表，查询性能大大降低。大数据量情况下，层级较深，检索速度慢。如下图 我们如果查询5这个值时，其查询了4次，这个还是数据比较少，如果数据比较多，那么就会形成很深的层级，查询性能大大降低。

看起来，层级变少了，查询5这个值只用了2步，但是红黑树也是一种二叉树，在数据比较多，也会形成很深的层级，查询性能也会较低，只是比二叉树好点

看来层级越少，查询性能越好，那有没有什么数据结构，在大数据情况下，层次也很少呢。有，下面开始介绍B-Tree

以一颗最大度数为5的b-tree为例（每个节点最多存储4个key，5个指针）,树的度数指的是一个节点的子节点个数。

B+Tree，非叶子节点不存储data，只存储索引（冗余），可以放更多的索引叶子节点包含所有索引字段，叶子节点用指针连接，提高区间访问的性能

以一颗最大度数（max-degree）为4（4阶）的b+tree为例：

为什么 MySQL 的索引要使用 B+ 树而不是其他树形结构?比如 B 树?

因为 B 树不管叶子节点还是非叶子节点，都会保存数据，这样导致在非叶子节点中能保存的指针数量变少(有些资料也称为扇出)。 指针少的情况下要保存大量数据，只能增加树的高度，导致 IO 操作变多，查询性能变低

为什么推荐使用整型的自增主键？

聚簇索引的数据的物理存放顺序与索引顺序是一致的，即：只要索引是相邻的，那么对应的数据一定也是相邻地存放在磁盘上的。 聚簇索引的顺序和磁盘中数据的存储顺序是一致的，如果主键不是自增id，那么可以想 象，它会干些什么，不断地调整数据的物理地址、分页，当然也有其他一些措施来减少这些操作，但却无法彻底避免。但，如果是自增的，那就简单了，它只需要一 页一页地写，索引结构相对紧凑，磁盘碎片少，效率也高。

Hash 哈希索引就是采用一定的hash算法，将键值换算成新的hash值，映射到对应的槽位上，然后存储在hash表中。 如果两个（或多个）键值，映射到一个相同的槽位上，他们就产生了hash冲突（也称为hash碰撞），可以通过链表来解决。

Hash索引特点 1.Hash索引只能用于对等比较（=，in），不支持范围查询（between，>，